\chapter{DAA protocol}
\label{cha:DAA protocol}
As noted in Chapter~\ref{cha:introduction}, the anonymous e-petitions system
requires, first, that the petition server can verify that the signatures were
signed by legitimate citizens. On the other hand, the system has to preserve the anonymity of citizens.
For this we turn to the DAA protocol. In this chapter, in addition to presenting
the main points of this protocol, we will also explain a number of concepts
necessary for full understanding of the protocol.
\section{Notation}
Throughout this chapter, the following notation is used.
We omit those considered basic notation and known by the reader.
\begin{enumerate}
  \item $\mathbb{Z}$ denotes the set of integers.
  \item $\mathbb{Q}$ denotes the set of rational numbers.
  \item $\mathbb{R}$ denotes the set of real numbers.
  \item When $A$ is a finite set, then $|A|$ denotes the number of elements in
  $A$.
  \item $a\in A$ denotes that the element $a$ is contained in the group $A$.
  \item $A \subseteq B$ denotes that  the set $A$ is a subset of the set $B$.
  \item $A \subset B$ denotes that the set $A$ is a proper subset of the set
  $B$. This means that $A \subseteq B$ and $A \neq B$.
  \item $A \cap B$ denotes the intersection of sets, $\{x|x \in A$  and  $x \in
  B\}$.
  \item $A \cup B$ denotes the union of sets, $\{x|x \in A$ or  $x \in B\}$.
  \item $A - B$ denotes the difference of sets, $\{x|x \in A$ and  $x \notin
  B\}$.
  \item $A  \times  B$ denotes the Cartesian product of sets, $\{(a,b)|a \in A$
  and $b \in B \}$.
  \item $a \equiv b$ denotes that $a$ is \emph{congruent} to $b$.
  \item $d = gcd(a, b)$ denotes that $d$ is the greatest common divisor of
  integers $a$ and $b$.
  \item Let A be an algorithm. By $A(\cdot)$ we denote that $A$ has one input, and
  by  $A_{(\cdot)}$ we will denote that $A$ is an indexed family of algorithms.
  \item $y\leftarrow A(x)$ denotes that $y$ is the result of running A on input
  $x$.
  \item Let $b$ be a boolean function, then $ ( y\leftarrow A(x) : b(y) )$
  denotes that $b(y)$ is true after $y$ was generated by running $A$ on input
  $x$
  \item Finally, the statement $Pr[ \{ x_i \leftarrow A_i(y_i) \}_{1\leq i \leq
  n }: b(x_n) ]=\alpha$ denotes that the probabity of $b(x_n)$ is TRUE, where
  $x_n$ is the result of running algorithms $A_1,A_2,\ldots ,A_n$ on inputs
  $y_1,y_2,\ldots , y_n$, is $\alpha$.
\end{enumerate}


\section{Abstract Algebra}

Abstract algebra is the field of mathematics that studies algebraic structures
such as groups, rings, or vector spaces. We mainly focus on one aspect of
abstract algebra, groups.




%\newcommand{\mydef}[1]{\begin{definition}#1\end{definition}}



\subsection{Groups}
\newenvironment{definition}[1][Definition]{\begin{trivlist}
\item[\hskip \labelsep \textbf{#1}]}{\end{trivlist}}

\begin{definition}[ Definition 1]
\label{3:binary_operation}
A \emph{binary operation}, written as $*$, on a set $G$  consists of a mapping
from $S$ $\times$ $S$ to $S$. It assigns to each ordered pair of elements from
$S$ an element of $S$.
\end{definition}

\begin{definition}[ Definition 2]
\label{3:group}
A \emph{group $(G,*)$}, is composed by a set $G$ with a binary operation $*$,
which satify the following axioms:
\begin{enumerate}[-- i --]
  \item The operation is \emph{associative}, this is, $a*(b*c)=(a*b)*c$ for all
  $a,b,c\in G$.
  \item There is an \emph{identity element, $i \in G$}, such that $a*i=i*a=a$
  for all $a \in G$.
  \item For each $a \in G$ there is an \emph{inverse element, $b \in G$} such
  that $a*b=b*a=i$.
  \newline
  \\
  The group is \emph{abelian} if it meets the following
  property:
  \item $a*b=b*a$ for all $a,b\in G$.
\end{enumerate}
For a \emph{multiplicative group}, the identity element is denoted by $1$ while
for an \emph{additive} is denoted by $0$. On the other hand, the inverse element
of a multiplicative group is denoted by $a^{-1}$ while for the additive groups,
it is denoted as $-a$.
\end{definition}

\begin{definition}[ Definition 3]
\label{3:subgroup}
A non-empty subset $H$ of elements of $G$ is a \emph{subgroup} if,
taking the operation of the group $G$, $H$ is also a group. Moreover, if $H$ is
a subgroup of $G$ and $H \neq G$, then $H$ is a \emph{proper subgroup of G}.
\end{definition}

\begin{definition}[ Definition 4]
\label{3:euler-phi-function}
Given $n \geq 1$, the \emph{Euler phi function}, written as $\phi (n)$,
denotes the number of integers in the interval $[1, n]$ that are relatively
prime to $n$.

Properties of Euler phi function:
\begin{enumerate}[-- i --]
  \item If $p$ is a prime, then $\phi (p) = p -1$.
  \item If $gcd(m,n)=1$, then $\phi (mn) = \phi (n) * \phi (m)$. That is why we
  say that Euler phi function is \emph{multiplicative}.
  \item If $n=p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}$ is the prime factorization
  of n, then: \newline
  $\phi (n)=n (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\ldots(1 - \frac{1}{p_k})$.
  
\end{enumerate}
\end{definition}

\begin{definition}[ Definition 5]
\label{3:integers-mod-n}
The set of integers ${0,1,2,\ldots,n-1}$ is called \emph{integers modulo n},
written as $\mathbb{Z}_n$. Addition, subtraction, and multiplication in
$\mathbb{Z}_n$ are performed modulo n.\end{definition}

\begin{definition}[ Definition 6]
\label{3:multiplicative-inverse}
Let $a,x \in \mathbb{Z}_n$. Then $x$ is called the \emph{multiplicative inverse
of a} if $ax=1 (mod$ $n)$. If this integer $x$ exists, it is unique and we
can say that $a$ is \emph{invertible}. The inverse element of $a$ is also
denoted as $a^{-1}$.
\end{definition}

\begin{definition}[ Definition 7]
\label{3:division}
If $a,b \in \mathbb{Z}_n$. Then the \emph{division} of $a$ by $b$ is $a*b^{-1}$.
It is only defined if $b$ is invertible modulo $n$.
\end{definition}

\begin{definition}[ Definition 8]
\label{3:multiplicative-group}

$\mathbb{Z}_n^*$ is a group of elements ${a | gcd(a,n) = 1}$. $\mathbb{Z}_n$ is
a \emph{multiplicative group}. The order of this group can be obtained just by calculating the Euler phi function.
\end{definition}


\begin{definition}[ Definition 9]
\label{3:order}
Given $a \in \mathbb{Z}_n^*$, the \emph{order} of $a$, denoted as $ord(a)$ is
the least positive integer t such that $a^t = 1 (mod$ $n)$.
\end{definition}

\begin{definition}[ Definition 10]
\label{3:generator}
Given $a \in \mathbb{Z}_n^*$, if $ord(a) = \phi(n)$ then $a$ is a
\emph{generator} of $\mathbb{Z}_n^*$. If $\mathbb{Z}_n^*$ has a generator, then
it is \emph{cyclic}.
\end{definition}

\begin{definition}[ Definition 11]
\label{3:quadratic-residue}
Given $a \in \mathbb{Z}_n^*$, if there is $x \in \mathbb{Z}_n^*$ such that
$x^2 = a$ then $a$ is a \emph{quadratic residue modulo n}. The set of all
quadratic residues modulo n is denoted as $Q_n$, and the set of quadratic
non-residues modulo n is $\bar{Q}_n$.
\end{definition}

\subsection{Strong RSA Assumption}

\begin{definition}[ Definition 12]
\label{3:RSA-modulus}
Let $p$ and $q$ be two prime numbers. An \emph{RSA modulus} $n$ is a number
resulting from the operation $pq=n$.
\end{definition}

\begin{definition}[ Definition 13]
\label{3:RSA-modulus}
Let $p$ and $q$ be two prime numbers. An \emph{RSA modulus} $n$ is a number
resulting from the operation $pq=n$. Consequently, the Euler phi function of
n is $\phi (n) = (p -1) (q - 1)$.
\end{definition}

\begin{definition}[ Definition 14]
\label{3:RSA-assumption}
Given a positive integer $e>1$, an RSA modulus $n$ and a random element $u \in
\mathbb{Z}_n^*$, the \emph{RSA assumption} states that it is hard to compute the
value $v \in
\mathbb{Z}_n^*$ such that:
$v^e = u  (mod$ $n) $.
\end{definition}

\begin{definition}[ Definition 15]
\label{3:safe-prime}
Given the prime numbers $p$ and $p'$, $p$ is a \emph{safe prime} if $p=2p'+1$.
The number $p'$ is known as \emph{Sophie Germain prime}.
\end{definition}

\begin{definition}[ Definition 16]
\label{3:Sepecial-RSA-modulus}
Let $n$ be an RSA modulus. If prime components $p$ and $q$ are safe primes, then
$n$ is a \emph{Special RSA modulus}. Moreover $Q_n$ is a cyclic group under
multiplication. Its order is $p'q'$ and all its elements, but $p'+q'$,  are
generators.
\end{definition}

\begin{definition}[ Definition 17]
\label{3:Strong-RSA-assumption}
Given a RSA modulus n and a random element $u \in
\mathbb{Z}_n^*$. The \textit{Strong RSA Assumption} states that it is
infeasible to find any pair ($v \in
\mathbb{Z}_n^*$, $e>1$) such that:
$u=v^e (mod$ $n)$.
\end{definition}


\section{Signature Schemes}

Digital signature schemes are a fundamental cryptographic
primitive (REFERENCE). They were invented at the same time as
public-key cryptography by Diffie and Hellman (REFERENCE)
and first built by Rivest, Shamir and Adleman (REFERENCE).
The first proposed digital signature schemes whose efficiency was
suitable for practical applications were secure under the Strong
RSA Assumption (REF-DEF). Specifically, in this thesis, we are interested in
using a digital signature scheme for constructing a system of anonymous
credentials.

A digital signature scheme is a mathematical scheme for demonstrating the
authenticity of a digital message or document. It basically consists of
three algorithms:
\begin{enumerate}[-i]
  \item Key Generation: $G(1^k) \to (PK,SK)$.
  \item Signature Algorithm: $Sign_{(SK)} (m) \to \alpha $.
  \item Verification Algorithm: $Verify_{(PK)} (m,\alpha) \to (TRUE  or FALSE)$.
\end{enumerate}

The features that every signature scheme possesses are: \emph{correctness} and
\emph{unforgeability}.
\begin{itemize}
  \item \textbf{Correctness:}\\
  Given a message $m$ in the message space $M_{(PK)}$, a public key PK and a secret key SK
  generated by $G(1^k)$, the output of
  the signing algorithm on $m$ using $SK$, that is, $\mathit{ \alpha =
  Sign_{(SK)}{(m)}}$, will always be accepted by the verifying algorithm,
  $\mathit{Verify_{(PK)}(m,\alpha)}$.
  \item \textbf{Unforgeability property:}\\
  The strong unforgeability is a property that ensures that a dishonest third
  entity cannot create a new signature from a previously signed message. In
  other words, suppose that this entity obtains the tuple $(m,\alpha)$ where
  $m$ is the original message and $\alpha$ its signature. A signature
  scheme is strongly unforgeable  if this dishonest entity cannot
  produce a new signature $\alpha '$ on $m$.
  
\end{itemize}




\section{Commitment schemes}
\label{3-comschemes}
A commitment scheme allows a user to commit to a specific value
without having to show it initially. Subsequently, this
value may be displayed. It can be seen as a sealed
envelope. In a commitment scheme every interaction consists of two phases:
\begin{itemize}
  \item The \textbf{commit phase}, in which the showing party selects and
  assigns a value.
  \item The \textbf{reveal phase}, in which the value shown by the showing
  party is verified by the verifying party.
\end{itemize}
In many occasions and in the simplest cases, the commit phase is only a single
message from the sender to receiver. This message is called \emph{commitment}.
The receiver must not know the value of
commitment during the commit phase. This fact is called ``hiding property".
On the other hand, the ``reveal phase" consists of another message, called
\emph{opening}, from sender to receiver, followed by a verification done by the
receiver. The value chosen during the commit phase must be the only one that the
sender can compute and that validates during the reveal phase, this is called
the binding property.
As stated in (REFERENCE), ``commitment schemes are the digital
analogue to nontransparent sealed envelopes".

A non-interactive commitment scheme is a triple (Setup, Commit, Open) such that:

\begin{enumerate}[-i]
  \item \textbf{Setup:} The public commitment key is generated:\newline
  $\mathit{ CK \leftarrow Setup( 1^k ) }$
  \item \textbf{Commit}: In this phase the sender generates a commitment/opening
  pair for a message $m \in M$.\newline
  $\mathit{ (c,d) \leftarrow Commit_{CK}(m) }$, where $c$ is the commitment
  value and $d$ is the opening value.
  \item \textbf{Open}: The commitment is opened and the value $\tilde{m}$ is
  obtained.\newline
  $Open_{CK}(c,d) \to \tilde{m}$
  
  This scheme must have the \emph{Correctness property}, this is, for every $c
  \in M$, $Open_{CK}(Commit_{CK}(m))=m$.
\end{enumerate}

\begin{figure}[h!]
\begin{centering}
\includegraphics[width=1\textwidth]{3-commitment.png}
\caption{Non-interactive commitment scheme'}
\label{fig:3-commitment}
\end{centering}
\end{figure}

In Figure ~\ref{fig:3-commitment} we can observe how a non-interactive
commitment scheme can be used. First, Alice generates the commitment key to be
used in the protocol (Step 1). Then she starts the ``commit phase'', generating a commitment value $c$ and an
openning value $d$ (Step 2). After generating these values she sends $c$ to Bob
(Step 3). Later, when she wants to open $m$, she sends $d$ to Bob (Step 4), who
runs $Open_{CK}(c,d) \to \tilde{m}$ (Step 5). By correctness, $m=\tilde{m}$ if
everybody is honest.

\newpage


\section{Zero knowledge proofs}

A proof of knowledge is a proof in which the prover succeeds in
``convincing'' a verifier that it knows something. As said before, in this
thesis the user will try to demonstrate to the petition server its citizenship.
However, the system must avoid that the petitions server learn more information
about the citizens identity after performing the proof. That is why the proofs
of knowledge used in this thesis must satisfy the zero knowledge property.


A zero-knowledge proof is a method where a party
tries to demonstrate to another party that a statement (usually mathematical) is
true, without revealing nothing but the veracity of  the affirmation. The entity that demonstrates
knowledge of a value is called ``prover'', while the other entity is called
``verifier''

A zero-knowledge proof must satisfy the following three properties:
\\
\begin{enumerate}
  \item \textbf{Completeness:}  if the statement is correct, an honest
  ``verifier" (that is, the one who follows the protocol properly) will be
  convinced by an honest ``prover".
  \item \textbf{Soundness:}  if the statement is false, no dishonest ``prover"
  will convince the honest "verifier", except with negligible probability.
  \item \textbf{Zero-knowledge:} if the statement is true, any
  dishonest ``verifier" cannot learn more information than this fact.
\end{enumerate}

Research in zero-knowledge proofs
has been motivated by authentication systems
where a party wants to prove his identity to
another through some secret information (for
example, a password), but it does not want the
second party learning anything about its secret.
Typical steps in an interactive zero knowledge proof
are:
\begin{enumerate}
  \item The prover sends a message of commitment to the verifier.
  \item The verifier answers with a challenge.
  \item The prover does some private calculations and sends a response to
  the verifier.
  \item The verifier accepts or rejects the answer (verification). If it
  rejects the answer, the protocol ends and the verifier does not accept that
  the prover possesses the secret.
  \end{enumerate}
  
It is possible to make a protocol non-interactive through the Fiat-Shamir
heuristic. Instead of letting the verifier choose the challenge, we compute the
hash function of the commitment. This way the verifier need not be involved at
all, the argument is non-interactive. We can hope that the argument is still sound
 and that it does not reveal any useful information. This hope is expressed in the random oracle
model, a heuristic model where we in security proofs replace the hash-function
with a random oracle. The random oracle assigns to each input (x, a) a random
string e.


  \subsection{ZK proofs about discrete logarithms}
  Here we explain a simple zero knowledge proof, analyzing its
  weak points and finally proposing a solution.
  
  \subsubsection{Schnorr protocol}
  
  In this zero-knowledge proof the prover must demonstrate the knowledge of a
  secret value $x$ to the verifier.
  
  We denote the public key by $y=g^x$, generated through $g$, generator of the
  group $G_q$. In order to demonstrate knowledge of the secret value, the prover commits to a
  random value $r$ (see Section ~\ref{3-comschemes})
  by calculating $t = g^r$ and sending it to the verifier (Figure
  ~\ref{3-schnorr}, Step 1). The verifier, after having received this value,
  answers to the prover with a challenge $c \in_R \{ 0,1\}^k $ (Step 2).
  The prover, calculates the response $s$ to the challenge by using the
  commitment ($t$), the challenge ($c$) and its secret value ($x$) as follows : $s
  = r - cx$ $mod$ $q$.
  Finally the verifier must verify if $g^sy^c = t$.\newline
  \\
  \textbf{Demo:} $g^sy^c=g^{(r-cx)}(g^x)^c=g^rg^{-cx}g^{cx}=g^r=t$.\newline
  \\
  
  \begin{figure}[h!]
\begin{centering}
\includegraphics[width=1.1\textwidth]{3-schnorr.png}
\caption{Schnorr protocol}
\label{3-schnorr}
\end{centering}
\end{figure}

However this protocol has several vulnerabilities. On the one hand,
a dishonest prover can pass the test if he knows the challenge that will
come even before generating $t$. In that case the prover could rig the
calculation and get a positive result. This is prevented by choosing a
challenge $c$ large enough.

On the other hand, we can have a dishonest verifier that calculates a
different challenge $c$ depending on the commitment received $t$. Thus
the verifier can obtain some information of the secret $x$.
One way to solve this attack is to precompute the challenges.



\subsubsection{The Schnorr protocol based on the group $QR_n$}

The above protocol showed a vulnerability if one of the two parties
was not honest. To prevent this we will use groups of hidden order,
in particular the group of quadratic residues with a Special RSA
modulus. The order of $QR_n$ is therefore $p'q'$. Calculating
the order of the $QR_n$ is as difficult as finding the prime factors of $n$.
It can only be approximated by the expression: $\lfloor \frac{n}{4} \rfloor$.
Moreover, almost all elements of this group are generators. The possibility
of finding an element non-generator is negligible.
Recall that all operations, except the calculation of the response $s$, are done
in $QR_n$ and so all operations are operations modulus $n$. This causes that $y=g^x$ is also a
generator of $QR_n$.

\begin{figure}[h!]
\begin{centering}
\includegraphics[width=1.1\textwidth]{3-schnorr-qr.png}
\caption{Schnorr protocol based on the group $QR_n$}
\label{3-schnorr-qr}
\end{centering}
\end{figure}

As we can see, now the prover does not know the order of $QR_n$ so the response
$s$ must be computed in $\mathbb{Z}$. Thus the verifier can infer some information
about the secret value $x$. If for example the verifier chooses a high value of
$c$ and the response's value is still high (remember that $s = r-cx$) this
means that the value of $x$ is very small. To avoid this, the random value $r$
is chosen to be much greater than $x$.


%%%%%%%%%%%%%%%DEBERIA METERLO%%%%%%%%%%%%%%%
% While many of these applications typically only exist on a specification level,
% a direction of applied research has produced first applications using ZK proofs
% that are deployed in the real world. The probably most prominent example is Direct
% Anonymous Attestation, which was adopted by the Trusted
% Computing Group (TCG), an industry consortium of many IT enterprises, as a
% privacy enhancing mechanism for remote authentication of computing platforms.
% Another example is the identity mixer anonymous credential system,
% which was released by IBM into the Eclipse Higgins project, an open source
% effort dedicated to developing software for user-centric identity management.
% Identity mixer is probably one of the most advanced protocol suites supporting
% the transient relationship paradigm.

ENOUGH??

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Anonymous credentials}

Anonymous credentials are a  booming part of
cryptography. They were proposed in
1985 by ChauM (reference) as an alternative to the certificates.
Credentials used in this thesis are based on zero-knowledge proofs.

In a credential system, a user can access a resource only by showing
a credential that demonstrates that he/she is authorised to do so.
This is equivalent to the identity card or passport which we used to prove a
person's identity. Its digital equivalent is the digital signature. The secret
key SK can be considered as the citizen's identity while
the credential is the signing of this secret key.
A credential system is anonymous if it allows citizens to show
those credentials without revealing their identity. This is exactly the purpose
of this project. In fact, when verifying the credentials, the verifier cannot
infer any information from the credential. The only information it can obtain is
that the user has the correct credentials. Additionally, an anonymous credential
system can allow the user to
get credentials anonymously.

Not all credential systems have the same degree of accountability. For our system
of credentials it will only be necessary to ensure that the user can only use
its credential once in a given context.
As a result of the protocol, a random number is generated. The reuse of the same
credential by the same user will result in the same number, so that the reuse
of the credential will be detected. On the other hand there is no way to relate
the same credential if it is used in different contexts, this property is called unlinkability.

\subsection{Camenisch-Lysyanskaya signature}

For our credentials system we need a commitment scheme and a signature scheme.
The signature scheme used in this thesis by the Credential Issuer, for the
creation and issuance of credentials, is the Camenisch-Lysyanskaya signature
(reference). This signature scheme requires the creation of a public key and a
private key by the Credential Issuer. \\

\begin{itemize}
  \item \textbf{Setup algorithm}
  
First, it creates an RSA modulus $n$ such that $n=pq$, where $p$ ans $q$ are
safe primes. Recall that a safe prime $p$ is obtained from the operation
$p=2p'+1$ where $p'$ is another prime. The set of $p$ and $q$ will be the
secret key. To compute the public key, the issuer chooses randomly the
following values: $R_0\ldots R_L,S,Z \in Q_n$ . The message to sign is
specifically a vector of messages with the same number of parameters than the
number of bases in the public key. Therefore, the message is:\\
$\{(m_0\ldots m_{L}) ; m_i \in \pm \{0,1\}^{l_m}\}$, where $l_m$ is the
length.  
  
  \item \textbf{Signing algorithm}
  
  In order to obtain the signature, the Credential Issuer chooses randomly a
prime number $e$ of length $l_v=l_n+l_m+l_r$. Note that $l_r$ is a security
parameter. Then the issuer has to find a value $A$ such that $Z=R_0^{m_0} S^v
A^e$. This is:\\
 $A=(\frac{Z}{R_^{m L-1} S_v})^\frac{1}{e}$.\\
As we can see, it is necessary to get the multiplicative inverse of $e$ in
order to get $A$.
Finally, the tuple $(A,e,v)$ will be our C-L signature.

  \item \textbf{Verification algorithm}
  
  On the other side, in order to run the verification algorithm, the
verifier entity, in our case the petition server, needs the signature $(A,e,v)$ and the
original message $m$. The verification is done by checking if the following
expressions hold:\\
\begin{itemize}
  \item $Z \equiv R^{m_0}\ldots R_{L-1}^{m_L-1} S^v A^e$
  \item $2^{l_e-1}<e<2^{l_e}$
  \end{itemize}
\end{itemize}
  \subsection{Camenisch-Lysyanskaya anonymous credential scheme}
More specifically, the concept used in this protocol is a signature of
  knowledge (also known as assertion-based signatures (REFERENCE)), linking the
  concepts of proof of knowledge and signature scheme, seen in the previous sections.
  In this protocol, instead of demonstrating knowledge
  of a certain value, it will be demonstrated the knowledge of a signature,
  obtained from an outside and trusted entity.
  
  Signatures of knowledge are signatures associated with an assertion that  must give the
  verifier all the necessary information to ensure that the
  prover meets the requirements for the signature. These statements involve
  assertions about attributes that have been checked and signed by a trusted entity.
  The signer can create and test the assertions in its signature by using only
  secret key material that is in its possession.
  
  The generation of this signature has an additional input, the certified
  attributes, which will be available as credentials issued by the credential
  issuer.  
  
  \section{Simplified DAA protocol}
  
  \subsection{Introduction}
  
  For the design of our system of anonymous credentials, we have chosen the
  Direct Anonymous Attestation protocol (DAA) as a starting point. This is
  mainly because it is the first privacy enhancing standardized anonymous
  credential protocol with features that makes it possible to distinguish
  between a small device with limited resources and a more powerful PC at
  the user side, commonly called the host. In our case the device with limited
  resources will be the smartcard while the host will be the mobile phone. Due
  to the limitations of the smartcard, all computations not involving the
  secret value stored in it, will be performed on the host. The host will also be responsible for establishing communication with the two
   servers: the credential issuer and the petition server.
   
At first you may think that user authentication to the verifier can be achieved
 only with a proof of knowledge of the secret value in the card. However, in
this case the tester would not distinguish if two proofs were performed by the
same card. This is why it is necessary a third entity, the credential issuer,
also called Privacy Certification Authority (PCA), shown in Figure. The name of
this entity is self-explanatory, this is the only entity responsible for issuing the
certificates required for the user's authentication to the verifier.

\begin{figure}[h!]
\begin{centering}
\includegraphics[width=0.9\textwidth]{3-daa_scheme.png}
\caption{Architecture of DAA scheme}
\label{3-daa-scheme} 
\end{centering}
\end{figure}

 Obviously,
before issuing this certificate, the issuer has to check whether the card is
valid or not. In the original DAA protocol this is done by using Endorsement
Keys (EK), in our case we have chosen to establish a client/server
authenticated channel between host
and issuer using the HTTPS protocol. Obviously there are more methods to
establish this authenticated channel.

 Once the user has been authenticated to
the issuer, they perform a two-party protocol to build the certificate
(credential), which will be stored by the user. This two-party protocol is called the Join Protocol.
 Once the user has the certificate, he performs a proof of knowledge to
 convince the verifier that  he has that certificate and the secret value needed
 to compute it. This step, which proves that the user has an anonymous
 attestation credential while signing a message, is called Signing protocol.
 
  It should be mentioned that this thesis does not implemented the original DAA
  protocol. It requires a greater number of parameters (such as pseudonyms or
  unfragmented values) and longer keys. We use a simplification of it but always
  maintaining the anonymity property and eliminating the possibility of manipulating credentials.
  
   The first change from the original DAA protocol is the use of the smartcard
    instead of a Trusted Platform Module (TPM). While both elements have a crypto processor, the TPM has a much more
complex specification.

The simplifications were made to help building a more understandable program and
allowing an easier implementation, error-free.

Note that these simplifications will obviously affect the security model of our system. This is taken into account
 for future improvements. The main simplifications are:
 
 \subsubsection{Pseudonyms}
We eliminate all the computations and parameters that have to do with pseudonyms
(both pseudonyms to the issuer and pseudonyms to the verifier). This has several
consequences: the issuer's keys are shorter and the signature is more simple. As
a result, the elimination of pseudonyms causes that our system can not
detect rogue cards. However, an anonymous credential system does not require this feature from the
 standpoint of consistency of credentials, as pseudonyms do not prevent the
 manipulation of credentials.

\subsubsection{Secret value}
 
 Instead of dividing it into two pieces and computing a hash of these two
 values, it has been chosen to work directly with the secret value, f. By not
 splitting the value f, the number of exponentiations on the card is reduced to
 only 2. This simplification increases the size of the value $e$ (belonging to
 the certificate), so there is a trade-off between time required to compute the
 value $e$ and the time to perform multiexponentiations. Due to the limitations
 of the card, this decision is to favor them.
 
 \subsubsection{Signature}
 
 In the original DAA protocol two commitments were computed to hide
    the certificate values $(A, e)$. Analyzing these operations we realize
    that both values can be combined into a single commitment so that our
    system still maintains the security properties.

\subsection{Final design}

The following mathematical specifications are the result of a number of simplifications
 made to the DAA protocol, aforementioned. The safety of this system is based on the same
  assumptions as the DAA protocol. Although some decisions decrease the security
  of the system, all the consequences have been taken into account when
  making simplifications. 

This thesis not only covers the implementation of the host and the card, but
  also the implementation of a real tester and an issuer organization. The
  following  paragraphs will explain: the generation of public and secret
  keys, the Join Protocol for the issuance of credentials and the
  Signing Protocol to show credentials.
  
  \subsubsection{Key generation}
  
  Before starting the protocol itself, it's necessary the creation and
  distribution of the issuer's public keys $(n,R,S,Z)$. To create these keys we
  will consider the above concepts Strong RSA Assumption and $QR_n$ generators.
  In order to generate the key, the issuer:
  
  \begin{itemize} 
    \item Creates $n \in \{ 0,1 \}^{l_n}$ such that it is a Special
    RSA Modulus.
    \item Chooses a random generator $S$ of the $QR_n$ group. For this, we will
    just choose a random number $ x \in Z_n$ an then we will calculate $S=x^2
    (mod \ n)$. Although this is not an exact approach, the possibility og
    getting a non generator number is negligible.
    \item  Next, it randomly chooses two numbers $x_o,x_z \in [ 1, p'q' ]$ and
    computes the following values:
    \begin{equation}
    	Z:=S^{x_z} (mod  \  n)
    \end{equation}
    \begin{equation}
    	R:=S^{x_0} (mod  \ n)
    \end{equation}
    
    The resulting values $Z$ and $S$ also belong to $QR_n$ since $S$ is a
    generator of $QR_n$	 and the order of the group is greater than  $x_0, x_z$.
    
  \end{itemize}
   
Finally we have a pair of keys: the values $(n,S,R,Z)$ form the public key while
$(p,q)$ is the secret key. 

In the original specification the host receives the issuer's public key and the
verifier checks this key once the host sends the signature. However, in our
 specification all the public keys will be sent at the beginning of the
 protocol.

  \subsubsection{Join protocol}
  
As noted above, in this part of the DAA protocol the user (remember that
 we call user the group formed by the smartcard and the host) gets a
 Camenisch-Lysyanskaya signature using its key secret. In
 the original protocol they are performed two proofs of knowledge, but in this
 protocol, for simplicity, they are omitted. Moreover, as noted above, we skip
 the use of pseudonyms.
 
 \begin{figure}[h!]
\begin{centering}
\includegraphics[width=1.1\textwidth]{3-join-protocol.png}
\caption{DAA's Join Protocol}
\label{3-join-protocol} 
\end{centering}
\end{figure}
 
  Messages sent by this protocol are shown in Figure ~\ref{3-join-protocol}. Keys PK and
 SK should be known in advance before starting the protocol. For the realization
  of this protocol we must take the following steps:
  
  \begin{itemize}
    \item The card chooses a value $v' \in \{ 0,1 \}^{l_n + l_\phi}$ and
    computes: 

\begin{equation}
U:=R^f S^v' (mod \ n)
\end{equation}
This value, as shown in messages 1 and 2 in Figure ~\ref{3-join-protocol}. Is sent to the
host, then the host will forward it to the credential issuer. At this point,
the mutually authenticated channel guarantees the correct identity of
both entities. As noted in the previous section, the value $f$ is the secret key of the card.
 Through the creation of $U$, the card proofs knowledge of his secrets $f$ and
 $v'$.
  
  \item Once the issuer receives the $U$ test, it chooses a value $\hat{v} \in
  \{ 0,1 \} ^l_v -1$ and a prime $e \in [ 2^{l_e -1} , 2^{l_e -1} + 2^{l_e' -1}
  ]$ and it computes its half of the shared secret $v''$ and the credential $A$:
  \begin{equation}
  v'':=\hat{v}+2^{l_v -1}
  \end{equation}
  \begin{equation}
  A:=(\frac{Z}{US^v''})^{\frac{1}{e}} (mod \ n)
  \end{equation}
  
  
  \end{itemize}
- 
  

